package 左哥算法.ch02二分;

import org.junit.Test;

import java.util.Arrays;

public class ch01_朴素快排 {
    public int[] sortArray(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    public void sort(int[] nums, int l, int r) {
        if (l >= r) return;
        int v = nums[r];
        int m = l;
        for (int i = l; i <= r; i++) {
            if (nums[i] <= v) {
                int temp = nums[i];
                nums[i] = nums[m];
                nums[m] = temp;
                m++;
            }
        }
        /**
         * 为什么不需要找到v的位置放到m-1处
         * 因为r位置是v，所以最后一次交换会将r位置替换为m-1位置
         */
        sort(nums, l, m - 2);
        sort(nums, m, r);
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 5, 4, 2};
        sortArray(arr);
        System.out.println(Arrays.toString(arr));
    }
}
